In recent years, more and more consumer appliances perform encryption processes for the purpose of copyright protection of digital content or secret data communications over networks. In such encryption processes, keys and ID data to be used in the processes need to be stored in appliances to use them. Safety of copyright protection systems and secure communication systems largely depend on confidentiality of the keys and the ID data. It is therefore necessary that such secret data is securely stored with protection against external analysis.
Conventional, typical methods for securely storing secret data include a method for storing data in a high-tamper-resistant hardware chip (tamper-resistant chip) and a method for embedding data in tamper-proof software. However, the former method has a problem that a special dedicated chip necessary for achieving high confidentiality for secret data is too costly. The latter method, on the other hand, generally cannot achieve such a high confidentiality that leaves little possibility of reveal of secret data through a long-time analysis.
Physically Unclonable Function (PUF) is a technique that can achieve high confidentiality of secret data without any special hardware such as a tamper-resistant chip. The PUF provides a method for storing secret data resistant to physical analysis by utilizing physical characteristics of devices. There are several specific methods for implementing the PUF. A silicon PUF disclosed in Patent Reference 1 is especially suitable for consumer appliances that are required to be less costly because the silicon PUF does not need special manufacturing environment or facilities to achieve high tamper resistance at less manufacturing cost.
(Overview of Silicon PUFs)
FIG. 1 shows a circuit configuration that implements a conventional silicon PUF. A PUF circuit 2000 shown in FIG. 1 is a circuit that outputs one-bit secret data when receiving a trigger signal.
The PUF circuit 2000 includes eight ring oscillators (a first ring oscillator 2001 to an eighth ring oscillator 2008), ring oscillator selecting units (a first ring oscillator selecting unit 2011 and a second ring oscillator selecting unit 2012) that each select one of the eight ring oscillators on the basis of input data, frequency counting units (a first frequency counting unit 2021 and a second frequency counting unit 2022) that count oscillation frequencies from the ring oscillators selected by the ring oscillator selecting units, and an output bit determining unit 2030 that determines an output bit of the PUF circuit 2000 on the basis of the counted frequencies. An operation of the PUF circuit 2000 is described below.
First, the ring oscillator selecting units 2011 and 2012 each select a predetermined ring oscillator from the eight ring oscillators 2001 to 2008. Next, the ring oscillators 2001 to 2008 receive a trigger signal to start oscillation operation. The frequency counting units 2021 and 2022 measure output signals from the ring oscillators selected by the ring oscillator selecting units 2011 and 2012 for oscillation frequencies of the ring oscillators, respectively. The output bit determining unit 2030 compares the two measured oscillation frequencies and determines an output bit of the PUF circuit 2000 on the basis of the magnitude ordering of the oscillation frequencies.
A trigger signal inputted into the PUF circuit 2000 causes the PUF circuit 2000 to determine only a one-bit output bit internally and output the output bit through the operation above. Even with the same configuration, such as the number of stages, the eight ring oscillators 2001 to 2008 have physical characteristics, such as delay, that are slightly different among them due to variations in a manufacturing process. Because of this, oscillation frequencies of the ring oscillators slightly differ from one another. The difference of the oscillation frequencies is determined unpredictably through manufacture of PUF circuits, and each of the PUF circuits has a unique oscillation frequency. Such oscillation frequencies make output bits mutually different. Correspondence between input data and output bits can be analyzed by measuring oscillation frequencies of ring oscillators in a PUF circuit. However, it is difficult to externally analyze the correspondence between input data and output bits of a PUF circuit because external analysis operation, such as probing, on the basis of oscillation frequencies affects physical characteristics of the ring oscillators, thereby preventing measuring the same oscillation frequencies as when output bits are calculated. Furthermore, PUF circuits can be manufactured less costly in environment and facilities for usual LSIs because they are fabricated as combinational circuits of ring oscillators, frequency counters and comparators without requiring special manufacturing environment or facilities.
(Problem of Silicon PUFs)
As described above, the silicon PUF technology enables low cost implementation of functions with input-output relations that are different from chip to chip and difficult to be analyzed. However, there are the following problems with silicon PUFs. Output bits of PUF circuit are determined by the magnitude ordering of oscillation frequencies of ring oscillators selected on the basis of input data. As mentioned above, differences in physical characteristics, such as delay, due to manufacturing variation cause differences in oscillation frequencies among ring oscillators. However, the magnitude ordering of two ring oscillators may be reversed due to environment change around them, such as temperature change, when the frequencies of the two ring oscillators are close together. For example, where two ring oscillators A and B are selected on the basis of an input data, and oscillation frequencies from them measures 1256 Hz and 1245 Hz, respectively, [the oscillation frequency of A]>[the oscillation frequency of B]; thus, the value of an output bit is determined as “1”. When the identical input data is inputted into the PUF circuit at a different time, the same ring oscillators A and B are selected. If temperature around the ring oscillators is higher in this case than the case before, delays in the ring oscillators increase, so that the oscillation frequencies decrease. However, since the oscillation frequencies decrease slightly differently between the two ring oscillators, the magnitude ordering may be reversed when original frequencies of the ring oscillators are close together. In this example, where the frequencies of the ring oscillators A and B differ only by 9 Hz, the magnitude ordering that [the oscillation frequency of A]>[the oscillation frequency of B] may be reversed due to temperature change. In other words, different output bits may be outputted for identical input data in some times, resulting in a problem with stability of values of output bits.
(Improvement of Silicon PUFs)
In order to address this problem, error-correction codes have been used in a conventional technique so as to increase stability by correcting output values (values of output bits) for errors.
FIG. 2 shows a configuration of an information security apparatus 3000 according to a conventional technique. The information security apparatus 3000 outputs a keyed hash value with a key generated using a PUF, for input data that has been externally inputted. The keyed hash value is generated using a keyed hash function. The keyed hash function is described on pages 189 to 195 of Non-patent Reference 1.
The information security apparatus 3000 includes an input unit 3001 that receives external input data, an output unit 3002 that outputs a keyed hash value, a hash generating unit 3003 that generates the keyed hash value, a PUF unit 3004 that generates a key using a PUF, error correcting unit 3005 that corrects the key for errors according to error-correction information and generates a hash key, and an error-correction information storage unit 3006 that stores the error-correction information.
The PUF unit 3004 includes a plurality of PUF circuits, for example, six PUF circuits 2000 and concatenates output bits from the PUF circuits to generate a six-bit key.
Operation of the information security apparatus 3000 is described below. The input unit 3001 receives external data and transmits a trigger signal to the PUF circuits 2000 in the PUF unit 3004. The PUF circuits 2000 generates output bits, and the PUF unit 3004 concatenates the output bits from the six PUF circuits 2000 to generate a key. Next, the error correcting unit 3005 corrects the key according to the error-correction information and generates a corrected hash key. Then, the hash generating unit 3003 generates a keyed hash value of the input data using the corrected hash key, and the output unit 3002 outputs the keyed hash value.
The error-correction information is determined by measuring values from the PUF circuits 2000 in the PUF unit 3004 when the information security apparatus 3000 is manufactured. More specifically, a plurality of keys generated by the PUF unit 3004 are surveyed to determine the most frequent key value, and then error-correction information is determined for the most frequent key value and stored in the error-correction information storage unit 3006.
Patent Reference 1: US 2003/0204743
Non-patent Reference 1: Tatsuaki Okamoto and Hirosuke Yamamoto, “GENDAI ANGOH”, Sangyo Tosho (1997)